Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

摘要

We present an $\tilde{O}(m^{10/7})=\tilde{O}(m^{1.43})$-time algorithm forthe maximum s-t flow and the minimum s-t cut problems in directed graphs withunit capacities. This is the first improvement over the sparse-graph case ofthe long-standing $O(m \min(\sqrt{m},n^{2/3}))$ time bound due to Even andTarjan [EvenT75]. By well-known reductions, this also establishes an$\tilde{O}(m^{10/7})$-time algorithm for the maximum-cardinality bipartitematching problem. That, in turn, gives an improvement over the celebratedcelebrated $O(m \sqrt{n})$ time bound of Hopcroft and Karp [HK73] whenever theinput graph is sufficiently sparse.